% Programs from Chapter 11 for depth-first and breadth-first search
% with some extensions made by Hans Guesgen.


% Depth-first search.
% Call by asking the question dfssolve([], Solution).

dfssolve(Node, Solution) :- depthfirst([], Node, Solution).

depthfirst(Path, Node, [Node | Path]) :- goal(Node).

depthfirst(Path, Node, Sol) :-
  s(Node, Node1),
  \+(member(Node1, Path)),
  depthfirst([Node | Path], Node1, Sol).

member(X, [X | Tail]).

member(X, [Head | Tail]) :-
  member(X, Tail).


% Breadth-first search:
% Call by asking the question bfssolve([], Solution).

bfssolve(Start, Solution) :- breadthfirst([[Start]], Solution).

breadthfirst([[Node | Path] | _], [Node | Path]) :- goal(Node).

breadthfirst([Path | Paths], Solution) :-
  extend(Path, NewPaths),
  conc(Paths, NewPaths, Paths1),
  breadthfirst(Paths1, Solution).

extend([Node | Path], NewPaths) :-
  bagof([NewNode, Node | Path], s(Node, NewNode), NewPaths),
  !.

extend(Path, []).

conc([], L, L).

conc([X | L1], L2, [X | L3]) :-
  conc(L1, L2, L3).

% My example model of the graphs from the first part of the course
s(a,b).
s(a,f).
s(a,e).

s(b,a).
s(b,g).
s(b,c).

s(c,b).
s(c,h).
s(c,d).

s(d,c).
s(d,i).
s(d,e).

s(e,d).
s(e,j).
s(e,a).

s(f,g).
s(f,a).
s(f,j).

s(g,f).
s(g,b).
s(g,h).

s(h,g).
s(h,c).
s(h,i).

s(i,h).
s(i,d).
s(i,j).

s(j,i).
s(j,e).
s(j,f).

goal(j).